#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
#define endl '\n'

LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}

LL get_ans(LL x, LL k)
{
    if(x == 1) return 0;
    vector<int> fac;
    for(int i = 1; i * i <= x; i++)
    {
        if(x % i == 0) 
        {
            fac.push_back(i);
            if(x / i != i) fac.push_back(x / i);
        }
    }
    sort(fac.begin(), fac.end());
    int n = fac.size();
    vector<int> dp(n, 100);
    dp[0] = 0;
    for(int i = 1; i < n; i++)
    {
        for(int j = i - 1; j >= 0; j--)
        {
            if(fac[i] / fac[j] > k) break;
            else
            {
                if(fac[i] % fac[j] == 0) 
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n - 1] == 100 ? -1 : dp[n - 1];
}

void solve() 
{
    LL x, y, k; cin >> x >> y >> k;
    LL g = gcd(x, y);
    LL ans = 0;
    x = x / g;
    y = y / g;
    LL ax = get_ans(x, k);
    LL ay = get_ans(y, k);
    if(ax == -1 || ay == -1) cout << -1 << endl;
    else cout << ax + ay << endl;

}


int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}